package com.copa.l1781;

/**
 * @author copa
 * @createDate 2022-12-12 15:52
 * @function 双重遍历法（优化版）
 */
public class Test2 {

    public int beautySum(String s) {
        if (s.length() < 2) {
            return 0;
        }
        int result = 0;
        // 优化 i遍历次数-2
        for (int i = 0; i < s.length() - 2; i++) {
            int[] record = new int[26];
            int max = 0;
            // 优化 遍历到只剩两个字符就无需遍历了
            if (s.length() - i > 2) {
                for (int j = i; j < s.length(); j++) {
                    int min = Integer.MAX_VALUE;
                    record[s.charAt(j) - 'a']++;
                    max = Math.max(max, record[s.charAt(j) - 'a']);
                    for (int k = 0; k < record.length; k++) {
                        if (record[k] > 0) {
                            min = Math.min(min, record[k]);
                        }
                    }
                    result += min == Integer.MAX_VALUE ? 0 : max - min;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "aabcb";
        System.out.println(new Test2().beautySum(s));
    }
}
